package com.gxc.tree;

/**
 * 平衡二叉树
 */
public class BalancedBinaryTree {

    public static void main(String[] args) {
        TreeBean tree = Preorder.createTree();
        TreeBean tree2 = Preorder.createNoBalancedBinaryTree();

        //递归判断是否平衡二叉树
        System.out.println(recursion(tree).isBbt);//true
        System.out.println(recursion(tree2).isBbt);//false
    }

    /**
     * 递归判断是否平衡二叉树
     * @param tree
     * @return
     */
    private static BalancedTreeInfo recursion(TreeBean tree) {
        if (tree == null) return new BalancedTreeInfo(0, true);

        BalancedTreeInfo leftTreeInfo = recursion(tree.left);
        if (!leftTreeInfo.isBbt) return leftTreeInfo;
        BalancedTreeInfo rightTreeInfo = recursion(tree.right);
        if (!rightTreeInfo.isBbt) return rightTreeInfo;

        if (Math.abs(leftTreeInfo.level - rightTreeInfo.level)>1)
            return new BalancedTreeInfo(Math.max(leftTreeInfo.level, rightTreeInfo.level)+1, false);
        return new BalancedTreeInfo(Math.max(leftTreeInfo.level, rightTreeInfo.level)+1, true);
    }

}
